package 力扣.双指针.最短区间;

import javax.security.auth.login.CredentialNotFoundException;
import java.util.HashMap;

public class 最小覆盖子串76 {
    //方法一：使用计数器map,这里要注意：两个引用类型Integer比较大小的时候要使用equal
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0){
            return "";
        }
        String ans = "";
        Counter counter1 = new Counter();
        final int tN = t.length();
        for (int i = 0; i < tN; i++) {
            counter1.add(t.charAt(i),1);
        }
        Counter counter2 = new Counter();
        final int sN = s.length();
        int eqNums = 0;
        int minAns = Integer.MAX_VALUE;
        int left = -1;
        for (int i = 0; i < sN; i++) {
            char c = s.charAt(i);
            counter2.add(c, 1);
            if (counter1.get(c).equals(counter2.get(c))){
                eqNums++;
            }
            if (i  - left < tN )continue;

            while (eqNums >= counter1.size()) {
                if (minAns > i - left){
                    minAns = i - left;
                    ans = s.substring(left + 1,i + 1);
                }
                char c1 = s.charAt(++left);
                if (counter1.get(c1).equals(counter2.get(c1))) {//两个引用类型之间的比较要使用equals
                    eqNums--;
                }
                counter2.add(c1, -1);
            }
        }
        return ans;
    }
    class Counter extends HashMap<Character,Integer> {
        public Integer get(Character key){
            return containsKey(key) ? super.get(key) : 0;
        }
        public void add(Character key,Integer value){
            put(key,get(key) + value);
            if (get(key) <= 0){
                remove(key);
            }
        }
    }

//方法二：使用数组计数
    public String minWindow2(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0){
            return "";
        }
        String ans = "";
        int[] ints = new int[256];
        int[] intt = new int[256];
        int left = -1;
        int Ns = s.length();
        int Nt = t.length();
        int len = 0;//一共有len个不同的字符
        for (int i = 0; i < Nt; i++) {
            int te = t.charAt(i) - 'A';
            if (intt[te] == 0){
                len++;
            }
            intt[t.charAt(i) - 'A']++;
        }
        int minLen = Integer.MAX_VALUE;
        int eqNum = 0;
        for (int i = 0; i < Ns; i++) {
            int te = s.charAt(i) - 'A';
            ints[te]++;
            if(ints[te] == intt[te]){//数量相等
                eqNum++;
            }
            if (i - left < Nt){continue;}
            while (eqNum == len){
                if (minLen > i - left){
                    minLen = i - left;
                    ans = s.substring(left + 1,i + 1);
                }
                int tee = s.charAt(++left);
                if (ints[tee - 'A'] == intt[tee - 'A']){
                    eqNum--;
                }
                ints[tee - 'A']--;//修改区间的状态
            }
            //此时区间(left,i)一定不满足条件
        }
        return ans;

    }
}
